\documentclass[unicode]{beamer}
\mode<presentation>
\usepackage{beamerthemesplit}
\usetheme{Malmoe}
%\usepackage[cp1251]{inputenc}
\usepackage[english]{babel}
%\usepackage[T2A]{fontenc}
\usepackage{amssymb,amsfonts,amsmath}
\usepackage {array}
\usepackage{graphicx}
\usepackage {gastex}
\usepackage{algorithm,algpseudocode}
\usepackage[]{color}%,dvips
\usepackage{pstricks,pst-node,pst-text}%,pst-3d
\definecolor{dred}{rgb}{0.6, 0, 0}


\algtext*{EndWhile}% Remove "end while" text
\algtext*{EndIf}% Remove "end if" text
\algtext*{EndFunction}% Remove "end function" text
\algtext*{EndProcedure}% Remove "end procedure" text
\algtext*{EndFor}% Remove "end for" text

\let\OldComment\Comment
\renewcommand{\Comment}[1]{\OldComment{\textcolor{gray}{#1}}}



\author[Dmitry Kosolobov]{Dmitry Kosolobov}
\title{Online Square Detection}

\institute[]{Ural Federal University\\ Ekaterinburg, Russia}
\begin{document}
\date{ }
\maketitle

\section{Introduction}

\begin{frame}
\frametitle{Introduction}
\begin{itemize}
\item<1-> A nonempty string $s$ is a \emph{square} if $s = xx$ for some string $x$
\item<2-> A string is \emph{squarefree} if it doesn't have a substring that is a square
\end{itemize}

\visible<3->{
\begin{block}{Example}
\begin{itemize}
\item<3-> $aa$, $abab$, $aaaa$ are squares
\item<4-> $s = abcaca$ is not squarefree since $s[3..6] = caca$ is a square
\end{itemize}
\end{block}
}
\end{frame}

\begin{frame}
\frametitle{Squarefree strings}
\begin{itemize}
\item<1-> Each string of length $\ge 4$ over two letter alphabet is not squarefree
\item<2-> There are infinitely many squarefree strings over three letter alphabet [Thue 1906]
\end{itemize}
\end{frame}

\section{Online Square Detection}

\begin{frame}
\frametitle{Online algorithms detecting squares}
\begin{block}{Main definition}
An algorithm \emph{online detects squares} if it processes the input string sequentially from left to right and decides whether each prefix is squarefree after reading the rightmost letter of that prefix
\end{block}
\visible<2->{
\begin{block}{Note}
There is an online algorithm detecting squares in $O(n^3)$ time and linear space
\end{block}
}
\end{frame}

\begin{frame}
\frametitle{Results}
\begin{itemize}
\item<2-> $\Omega(n\log n)$; unordered alphabet [Main, Lorentz 1985]
\item<6-> $\Theta(n\log n)$; unordered alphabet [Apostolico, Breslauer 1996]
\item<3-> $O(n\log^2 n)$; unordered alphabet [Leung, Peng, Ting 2004]
\item<4-> $O(n\log n)$; ordered alphabet [Jansson, Peng 2005]
\item<5-> $O(n\log\sigma)$; ordered alphabet [Hong, Chen 2008]\visible<7->{$\leftarrow$ impractical}
\end{itemize}
\visible<8->{
\begin{block}{Theorem}
There is an online algorithm detecting squares in $\Theta(n\log n)$ time and linear space on unordered alphabet
\end{block}
}
\visible<9->{
\begin{block}{Theorem}
There is an online algorithm detecting squares in $O(n\log\sigma)$ time and linear space on ordered alphabet
\end{block}
}
\end{frame}

\section{Catcher}

\newlength\lunderset
\newlength\rulethick
\lunderset=1.5pt\relax
\rulethick=.8pt\relax
\def\stackalignment{l}
\newcommand\nunderline[2][1]{\setbox0=\hbox{#2}%
  \stackunder[#1\lunderset-\rulethick]{\strut#2}{\rule{\wd0}{\rulethick}}}

\begin{frame}
\frametitle{Borders}
A \emph{border} of a string $w$ is a string that is both a proper suffix and a proper prefix of $w$
\uncover<2->{
\begin{block}{Example}
Borders of \only<2>{$abcabca$}\only<3>{$\textcolor{red}{a}bcabc\textcolor{red}{a}$}%
\only<4->{{$\textcolor{red}{abc}\textcolor{dred}{a}\textcolor{red}{bca}$}}: \visible<3->{$a$}\visible<4->{, $abca$}
\end{block}
}
\end{frame}

\begin{frame}
\frametitle{Key lemma}
\begin{itemize}
\item let $text$ be a string of length $n$
\item<2-> $text[1..n{-}1]$ is squarefree
\item<3-> $text[k..n] = xx$ for some $x$ and $k < n$
\item<4-> $i\le k \le j$ for some $i$, $j$ such that $j - i < n - j$
\end{itemize}
\visible<5->{
\begin{figure}[htb]
\vskip-4mm
\includegraphics[scale=0.55]{square1}
\vskip-4mm
\end{figure}
}
\visible<6->{
\begin{block}{Lemma}
$x''$ is the longest border of $text[j{+}1..n]$.
\end{block}
}
\end{frame}


\begin{frame}
\frametitle{Catcher}
\emph{Catcher} covering the block $[i..j]$ of the string $text[1..n]$
\begin{itemize}
\item<2-> $text[1..n{-}1]$ must be squarefree
\item<3-> $j - i < n - j$
\item<4-> $j - i + 1$ is the length of the catcher
\item<5-> once a letter is appended to the right of $text$, if $text[k..n]$ is a square for some $k\in [i..j]$, the catcher detects this square
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Implementation}
\begin{itemize}
\item our catcher contains integer variables $b$ and $s$
\item<2-> $b$ is the length of the longest border of $text[j{+}1..n]$
\item<3-> if $j - i + 1 \ge n - j - 2b$, $s$ equals the length of the longest suffix of $text[i..j]$ that is a suffix of $text[j..n{-}b]$
\visible<3->{
\begin{figure}[htb]
\vskip-3mm
\includegraphics[scale=0.40]{square}
\vskip-4mm
\end{figure}
}
\item<4-> otherwise, $s$ equals zero
\item<5-> if $2b + s \ge n - j$, a square is detected
\end{itemize}
\end{frame}

%\begin{frame}
%\frametitle{Pseudocode of the catcher}
%\begin{algorithmic}[1]
%\State read a letter and append it to $text$ (thereby incrementing $n$)
%\State compute $b$ by the algorithm of [Knuth, Morris, Pratt 1977]
%\If{$b \ne b_{old} + 1$}
%    \State $s \gets 0$
%\EndIf
%\If{$j - i + 1 \ge n - j - 2b \mathrel{\mathbf{and}} s = 0$}
%    \While{$j - s \ge i \mathrel{\mathbf{and}} text[n{-}b{-}s] = text[j{-}s]$}
%        \State $s \gets s + 1$ \Comment{compute $s$ by a naive algorithm}
%    \EndWhile
%\EndIf
%\If{$2b + s \ge n - j$}
%    \State the square suffix of the length $2(n - j - b)$ is detected
%\EndIf
%\end{algorithmic}
%\begin{figure}[htb]
%\vskip-4mm
%\includegraphics[scale=0.40]{square}
%\vskip-4mm
%\end{figure}
%\end{frame}

\begin{frame}
\frametitle{Working time and space}
\begin{block}{Lemma}
The catcher requires $O(n - j)$ time and space.
\end{block}
\visible<2->{\emph{Proof is not obvious}}
\end{frame}


\section{Algorithm for unordered alphabet}

\begin{frame}
\frametitle{Algorithm}
\begin{block}{Idea}
We maintain a set of catchers covering the string $text[1..n{-}1]$
\end{block}
\begin{itemize}
\item<2-> denote $p_k = \lfloor n / 2^k\rfloor - 1$ for each $k \in [0 .. \lfloor\log n\rfloor{-}1]$
\item<3-> one catcher covers $[(p_k{-}1)2^k{+}1 .. p_k2^k]$
\item<4-> if $p_k$ is even, another covers $[(p_k{-}2)2^k{+}1 .. (p_k{-}1)2^k]$
\item<5-> this system of catchers covers $text[1..n{-}1]$
\end{itemize}
\visible<6->{
\begin{figure}[htb]
\vskip-4mm
\includegraphics[scale=0.55]{systraps}
\vskip-4mm
\end{figure}
}
\end{frame}

\begin{frame}
\frametitle{Analysis of the algorithm}
\begin{algorithmic}[1]
\State read a letter and append it to $text$ (thereby incrementing $n$)
\For{$(k \gets 0;\; 2^k \le n/2 \mathrel{\mathbf{and}} (n \bmod 2^k) = 0;\;k \gets k + 1)$}
    \State $p \gets \lfloor n / 2^k\rfloor - 1$
    \State create a catcher covering $\overline{(p{-}1)2^k{+}1,p2^k}$
    \If{$(p \bmod 2) \ne 0 \mathrel{\mathbf{and}} p > 1$}
        \State remove previous catchers covering blocks of length $2^k$
    \EndIf
\EndFor
\end{algorithmic}
\begin{itemize}
\item<2-> the catcher of length $2^k$ requires $O(2^k)$ time and space
\item<3-> at any time there are at most two catchers of length $2^k$
\item<4-> all catchers take $O(\sum_{k=0}^{k=\lfloor\log n\rfloor{-}1} 2^k) = O(n)$ space
\item<5-> the catchers of length $2^k$ take overall $O(2^k \frac{n}{2^k}) = O(n)$ time
\end{itemize}
\visible<6->{The algorithm runs in $O(n\log n)$ time and $O(n)$ space}
\end{frame}

\begin{frame}
\frametitle{Open problems}
\begin{itemize}
\item Is there an online algorithm detecting squares in $O(n)$ time for ordered alphabet?
\item Can we efficiently support ``rollback'' operation, i.e., the operation that cuts off a suffix of arbitrary length from the read string?
\end{itemize}
\visible<2->{\center{\Huge{Thank you for your attention!}}}
\end{frame}

\end{document} 